package com.leetcode.algorithm.y19.m04;

/**
 * leetcode-cn.com
 * (done)80. 删除排序数组中的重复项 II
 * (done)88. 合并两个有序数组
 * (done)75. 颜色分类
 * @author: jie.deng
 * @time: 2019年4月19日 上午10:43:06
 */
public class MySolution0419 {
    
    /**
     * 80. 删除排序数组中的重复项 II
     * 
     * 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
     * 
     * 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
     * 
     * 示例 1:
     * 
     * 给定 nums = [1,1,1,2,2,3],
     * 
     * 函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
     * 
     * 你不需要考虑数组中超出新长度后面的元素。
     * 示例 2:
     * 
     * 给定 nums = [0,0,1,1,1,1,2,3,3],
     * 
     * 函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。
     * 
     * 你不需要考虑数组中超出新长度后面的元素。
     * 说明:
     * 
     * 为什么返回数值是整数，但输出的答案是数组呢?
     * 
     * 请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
     * 
     * 你可以想象内部操作如下:
     * 
     * // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
     * int len = removeDuplicates(nums);
     * 
     * // 在函数里修改输入数组对于调用者是可见的。
     * // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
     * for (int i = 0; i < len; i++) {
     *     print(nums[i]);
     * }
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        // 数组类的通用解法
        // 做好初始定义:需要定义一个变量，明确该变量的定义，并且在书写整个逻辑的时候，要不停的维护住这个变量的意义。
        if (nums == null) {
            return 0;
        }
        int len = nums.length;
        if (len <= 2) {
            return len;
        }
        int newLen = 2; // 原地操作数组nums，newLen定义为符合题意的数组的长度，即下一个待插入元素的索引
        for (int i = 2; i < len; i++) {
            if (!(nums[i] == nums[newLen - 1] && nums[i] == nums[newLen - 2])) {
                nums[newLen++] = nums[i];
            }
        }
        return newLen;
    }
    
    /**
     * 88. 合并两个有序数组 
     * 给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
     * 
     * 说明:
     * 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 
     * 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 
     * 
     * 示例:
     * 输入: nums1 = [1,2,3,0,0,0], m = 3; nums2 = [2,5,6], n = 3
     * 输出: [1,2,2,3,5,6]
     * 
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int idx = m + n - 1;
        // 尾插法
        while (m > 0 && n > 0) {
            if (nums2[n - 1] > nums1[m - 1]) {
                nums1[idx--] = nums2[n - 1];
                n--;
            } else {
                nums1[idx--] = nums1[m - 1];
                m--;
            }
        }
        if (m == 0) {
            while (n > 0) {
                nums1[idx--] = nums2[n - 1];
                n--;
            }
        }
    }
    
    /**
     * 75. 颜色分类
     * 
     * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
     * 
     * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     * 
     * 注意:
     * 不能使用代码库中的排序函数来解决这道题。
     * 
     * 示例:
     * 
     * 输入: [2,0,2,1,1,0]
     * 输出: [0,0,1,1,2,2]
     * 进阶：
     * 
     * 一个直观的解决方案是使用计数排序的两趟扫描算法。
     * 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
     * 你能想出一个仅使用常数空间的一趟扫描算法吗？
     * @param nums
     */
    public void sortColors(int[] nums) {
        // 解题思路:
        // 1.从左边开始，找第一个非0的元素pivot，经过一趟快速排序，使其左边都是小于pivot，右边都不小于pivot
        // 2.在剩余的未排序的数组中，通过首尾指针碰撞，交换不符合的数据
        int idx = 0;
        int len = nums.length;
        // 1.从左边开始，找第一个非0的元素pivot，经过一趟快速排序，使其左边都是小于pivot，右边都不小于pivot
        while (idx < len && nums[idx] == 0) {
            idx++;
        }
        if (idx == len) {
            // 全是0的情况
            return;
        }
        int pivot = nums[idx];
        int left = idx;
        int right = len - 1;
        while (left < right) {
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            if (left < right) {
                nums[idx] = nums[right];
                idx = right;
            }
            while (left < right && nums[left] < pivot) {
                left++;
            }
            if (left < right) {
                nums[idx] = nums[left];
                idx = left;
            }
        }
        nums[idx] = pivot;

        // 2.在剩余的未排序的数组中只有两个数(1和2 或者 0和1)，通过首尾指针碰撞，交换不符合排序规则的数据
        int min = 0; // 待排序的数组中较小的数
        if (pivot == 1) {
            left = idx + 1;
            right = len - 1;
            min = 1;
        } else {
            left = 0;
            right = idx - 1;
        }
        while (left < right) {
            while (left < right && nums[left] == min) {
                left++;
            }
            while (left < right && nums[right] == min + 1) {
                right--;
            }
            if (left < right) {
                nums[left] = nums[left] ^ nums[right];
                nums[right] = nums[left] ^ nums[right];
                nums[left] = nums[left] ^ nums[right];
                left++;
                right--;
            }
        }
    }
}
